Trong lý thuyết độ phức tạp tính toán, chứng minh có thể kiểm chứng ngẫu nhiên (PCP - viết tắt của probabilistically checkable proof) là một chứng minh có thể được kiểm tra bởi một thuật toán ngẫu nhiên sử dụng một số lượng nhỏ bit ngẫu nhiên và một số lượng nhỏ bit của chứng minh. Thuật toán sau đó phải chấp nhận chứng minh đúng và từ chối chứng minh sai với xác suất cao. Chứng minh sử dụng trong định nghĩa dựa trên thuật toán kiểm chứng của NP cũng thỏa mãn 2 yêu cầu này, bởi thuật toán kiểm chứng đọc toàn bộ chứng minh một cách tất định và chấp nhận chứng minh đúng, từ chối chứng minh sai. Tuy nhiên, điều thú vị ở đây là sự tồn tại của chứng minh có thể kiểm chứng được bằng cách chỉ đọc một vài bit của chứng minh cùng với việc sử dụng bit ngẫu nhiên một cách khôn ngoan.Chứng minh có thể kiểm chứng ngẫu nhiên tạo ra nhiều lớp độ phức tạp tính toán khác nhau, phụ thuộc vào số lượng bit cần đọc của chứng minh, và số lượng bit ngẫu nhiên cần sử dụng. Lớp PCP ( r ( n ) , q ( n ) ) {\displaystyle (r(n),q(n))} là tập hợp các bài toán quyết định có chứng minh có thể kiểm chứng ngẫu nhiên sử dụng tối đa r ( n ) {\displaystyle r(n)} bit ngẫu nhiên và đọc tối đa q ( n ) {\displaystyle q(n)} bit của chứng minh. Thông thường, chứng minh đúng luôn được chấp nhận và chứng minh sai bị từ chối với xác suất ít nhất 1/2. Định lý PCP chứng minh rằng PCP ( O ( log ⁡ n ) , O ( 1 ) ) = {\displaystyle (O(\log n),O(1))=} NP.